/**
 * 大集合A
 * 分成小集合a,b
 * a,b的长度为n1,n2
 * a,b的元素和为s1,s2
 * 要求n1和n2最接近，s1和s2相距最远
 * 
 * 一个大前提，一个小前提
 * 首先保证对半分，再要求和的差最小
 * 使用快速排序的思想，这里使用low()表示向下取整
 * 若i=low(n/2)，则分组完毕，结束
 * 若i<low(n/2),则左侧的属于a，右侧的继续划分
 * 若i<low(n/2),则右侧的属于b，左侧侧的继续划分
 *
 * 时间复杂度O(n)
 * 空间复杂度O(1)
 * 
 */
int partition(int a[],int n){
    //low0  high0 是记录原始的开始结束下标的，找枢纽位置之前
    //low   high  是记录当前下标，用来找枢纽的
    int pivotkey,low=0,low0=0,high=n-1,high0=n-1,flag=1,k=n/2,i;
    int s1=0,s2=0;
    while (flag){
        pivotkey=a[low];
        while (low<high){//找枢纽位置
            while (low<high&&a[high]>=pivotkey){
                --high;
            }
            if(low!=high) a[low]=a[high];
            while (low<high&&a[high]<=pivotkey){
                ++low;
            }
            if(low!=high)a[high]=a[low]; 
        }
        a[low]=pivotkey;//将枢纽放到正确的位置

        //和之前一样，这里下标都是原始数组的下标，不会因为分裂导致下标重新从0计数
        if(low==k-1) flag=0;//当flag=0的时候就可以退出循环了
        else{
            if(low<k-1){ //如果枢纽靠左，那么下一次遍历在右半数组找
                low0=++low;
                high=high0;
            }else{
                high0=--high;
                low=low0;
            }
        }
    }
    //计算和
    for(i=0;i<k;i++) s1+=a[i];
    for(i=k;i<n;i++) s2+=a[i];
    //计算和的差
    return s2-s1;
}